package com.company.zijie;

import java.util.*;
//接雨水问题https://leetcode-cn.com/problems/trapping-rain-water/
public class trap {
    public static void main(String[] args) {
        int[] input = {5,2,1,4,3};
        System.out.println(helper(input));
    }
    //1.暴力,每个高度nums[i]所能接到的最大蓄水量
    public static int helper(int[] nums){
        if(nums.length < 3) return 0;
        int n = nums.length;
        int ret = 0;
        for(int i = 0; i<n; i++){

            int leftBase = 0;
            int rightBase = 0;
            //找出左侧最高
            for (int j = i-1; j >=0 ; j--) {
                if (nums[j]>leftBase) leftBase = nums[j];
            }
            //找到右侧最高
            for (int j = i+1; j <n ; j++) {
                if (nums[j]>rightBase) rightBase = nums[j];
            }
            //计算当前柱子可以接到的蓄水量
            int base = Math.min(leftBase, rightBase);
            if (base>nums[i]){
                ret += base-nums[i];
            }
        }
        return ret;
    }
}